Graf dirigit

Un graf dirigit o dígraf és un tipus de graf en el qual les arestes tenen un sentit definit,^[1] a diferència del graf no dirigit, en què les arestes són relacions simètriques i no apunten a cap lloc.

De vegades, un dígraf s’anomena dígraf simple per distingir-lo del cas general del multigraf dirigit, on els arcs constitueixen un multiconjunt, en lloc d’un conjunt. En aquest cas, pot haver-hi més d’un arc que unisca dos vèrtexs en la mateixa direcció, distingint-se mútuament per la seva identitat, pel seu tipus (per exemple, un tipus d’arc representa relacions d’amistat mentre l’altre tipus representa missatges enviats recentment entre el nodes), o per un atribut com la seva importància o pes. Sovint també es considera que en un simple dígraf no es permeten els bucles.